package com.yun.algorithmproblem.leetcode;

import java.util.*;

public class Leetcode1129 {
    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        int[] answer=new int[n];
        int[][] dist = new int[2][n];//0号数组代表红色路径,1号数组代表蓝色路径
        Queue<int[]> queue = new LinkedList<>();
        List<Integer>[][] g = new List[n][2];

        for (int i = 0; i <= 1; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
            dist[i][0] = 0;
        }

        for (int i = 0; i < n; i++) {
            g[i][0] = new ArrayList<>();//red
            g[i][1] = new ArrayList<>();//blue
        }
        for (int[] redEdge : redEdges) {
            g[redEdge[0]][0].add(redEdge[1]);
        }
        for (int[] blueEdge : blueEdges) {
            g[blueEdge[0]][1].add(blueEdge[1]);
        }

        queue.offer(new int[]{0, 0});
        queue.offer(new int[]{1, 0});
        while (!queue.isEmpty()) {
            int[] currNode = queue.poll();
            int color = currNode[0], currNum = currNode[1];
            for (Integer next : g[currNum][color]) {
                if (dist[1 - color][next] <= dist[color][currNum] + 1) {
                    continue;
                }
                dist[1 - color][next] = dist[color][currNum] + 1;
                queue.offer(new int[]{1-color,next});
            }
        }
        for (int i = 0; i < n; i++) {
            int min=Math.min(dist[0][i],dist[1][i]);
            if(min==Integer.MAX_VALUE){
                min=-1;
            }
            answer[i]=min;
        }
        return answer;
    }
}
